package test;

import com.alibaba.fastjson2.JSON;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @author sunzhuokun
 * @date 16:54 2024/5/14
 * @description 区间交集
 * 给定一组闭区间，其中部分区间存在交集。任意两个给定区间的交集，称为公共区间(如:[1,2],[2,3]的公共区间为[2,2]，[3,5],[3,6]的公共区间为
 * [3,5])。公共区间之间 若存在交集，则需要合并(如:[1,3],[3,5]区间存在交集[3,3]，需合并为[1,5])。按升序排列 输出合并后的区间列表。
 * <p>
 * 输入描述: 一组区间列表，区间数为 N: 0<=N<=1000;区间元素为 X: -10000<=X<=10000。
 * 输出描述: 升序排列的合并区间列表
 * <p>
 * 备注:
 * 1、区间元素均为数字，不考虑字母、符号等异常输入。
 * 2、单个区间认定为无公共区间。
 * 示例:
 * 输入
 * [[0, 3], [1, 3], [3, 5], [3, 6]]
 * 输出
 * [[1, 5]]
 */
public class IntervalIntersection_区间交集 {

    public static void main(String[] args) {
//        int[][] intervals = {{0, 3}, {1, 3}, {3, 5}, {3, 6}};
        int[][] intervals = {{1, 3}, {3, 5}};
        List<int[]> mergedIntervals = merge(intervals);
        System.out.println(JSON.toJSONString(mergedIntervals));
    }

    private static List<int[]> merge(int[][] intervals) {
        if (intervals.length <= 1) {
            return Arrays.asList(intervals);
        }

        // 按照区间结束值排序
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

        System.out.println(JSON.toJSONString(intervals));

        Stack<int[]> stack = new Stack<>();
        stack.push(intervals[0]);

        for (int i = 1; i < intervals.length; i++) {
            if (stack.isEmpty()) {
                stack.push(intervals[i]);
                continue;
            }

            int[] top = stack.peek();
            // 存在交集，合并区间
            if (intervals[i][0] <= top[1]) {
                stack.pop();
                int[] merged = {Math.min(top[0], intervals[i][0]), Math.max(top[1], intervals[i][1])};
                stack.push(merged);
            } else {
                // 没有交集，直接压栈
                stack.push(intervals[i]);
            }
        }
        return new ArrayList<>(stack);
    }


}
